package com.leetcode.LeetCode精选TOP面试题;

import com.leetcode.common.model.TreeNode;
import java.util.HashMap;
import java.util.Map;

/**
 * @author 覃国强
 * @date 2022-06-15 17:17
 */
public class 题库_0105_从前序与中序遍历序列构造二叉树 {

  static
  class Solution {
    public TreeNode buildTree(int[] preorder, int[] inorder) {
      if (preorder == null || preorder.length == 0) {
        return null;
      }
      Map<Integer, Integer> inorderMap = new HashMap<>();
      for (int i = 0; i < inorder.length; ++i) {
        inorderMap.put(inorder[i], i);
      }
      return helper(preorder, 0, inorderMap, 0, inorder.length - 1);
    }

    public TreeNode helper(int[] preorder, int father, Map<Integer, Integer> inorderMap, int l, int r) {
      if (l > r) {
        return null;
      }
      int value = preorder[father];
      TreeNode root = new TreeNode(value);

      Integer index = inorderMap.get(value);
      int leftFather = father + 1;
      int rightFather = father + (index - l) + 1;

      root.left = helper(preorder, leftFather, inorderMap, l, index - 1);
      root.right = helper(preorder, rightFather, inorderMap, index + 1, r);
      return root;
    }
  }

}
